#ifndef EXPRESSIONTREE_H_INCLUDED
#define EXPRESSIONTREE_H_INCLUDED
#include <vector>
#include <stack>
#include <string>
#include <iostream>
#include<stdlib.h>
#include <unistd.h>
using namespace std;

class expTree{
    struct Node{

        Node * left;
        Node * right;
        string value;
        Node(string v, Node * l = NULL, Node * r = NULL):value(v), left(l),right(r){}
    };
public:


    inline void init()
    {
        string temp;
        while(cin >> temp)
        {
            if(temp == "finish")
                break;
            myStrVec.push_back(temp);
        }
    }

    inline bool isOpNum(int index)
    {
        return isalpha(myStrVec[index][0]);
    }

    inline bool isOpSymbol(int index)
    {
        return ispunct(myStrVec[index][0]);
    }

    void buildTree()
    {
        for(int i = 0; i < myStrVec.size(); ++i)
        {
            /*push operate number to stack*/
            if(isOpNum(i)){
                cout << "push " << myStrVec[i] << endl;
                Node * newnode = new Node(myStrVec[i]);
                mystack.push(newnode);
            }
            else if(isOpSymbol(i))
            {

                Node * a = mystack.top();
                cout << "pop " << a->value << endl;
                mystack.pop();
                Node * b = mystack.top();
                cout << "pop " << b->value << endl;
                mystack.pop();
                Node * newnode = new Node(myStrVec[i], a , b);
                cout << "push " << myStrVec[i] << endl;
                mystack.push(newnode);
            }
        }
    }

    void printTree()
    {

        Node * root = mystack.top();
        //mystack.pop();
        cout << "root is " << root->value << endl;
        printTree(root);
        cout << endl;
    }

    void removeall()
    {
        Node * root = mystack.top();
        mystack.pop();
        removenode(root);

    }

    void printTree(Node * nodeptr)
    {
        if(nodeptr == NULL)
            return;

        if(nodeptr->left != NULL && nodeptr->right != NULL)
            cout << "(";
       printTree(nodeptr->left);


        cout << nodeptr->value << " ";


        printTree(nodeptr->right);

        if(nodeptr->left != NULL && nodeptr->right != NULL )
            cout << ")";
    }


    ~expTree()
    {

    }


    void removenode(Node * n)
    {
        /*postorder*/
        if(n == NULL)
            return;
        removenode(n->left);
        removenode(n->right);
        cout << "remove " << n->value << endl;
        delete n;
        n = NULL;
    }

private:
    stack<Node * > mystack;

    vector<string> myStrVec;


};


#endif // EXPRESSIONTREE_H_INCLUDED
